Algorithm: Analysis and Theory (2017)

基本信息 (General Information)

Level: Postgraduate

Time & Place: 10:00 am -- 11:40 am, Monday & Thursday，Chen Rui Qiu Building 219（陈瑞球楼 219）

Instructor:

Name: Xiaofeng Gao
Email: gao-xf(at)cs.sjtu.edu.cn
Office: Telecom Building 3-328
Phone: 021-34207407

Teaching Assistant:

Name: Jiaxi Liu (刘家玺)
Email: jsxzljx@163.com
Office: SEIEE 3-328
Phone: 34207407
Office Hour:

Name: Shuang Wu (吴双)
Email: steinsgate@sjtu.edu.cn
Office: SEIEE 3-328
Phone: 34207407
Office Hour:

课堂时间 (Course Schedule)

计划日程 (Syllabus)

Week	Date	Lecture Topic	Event	TA
1	Feb.20	Syllabus, Preliminary, Introduction to Algorithm Schedule, Grading Policy, Preliminary, Basic Introduction, etc.
1	Feb.23	Algorithm Design and Analysis Sorting Algorithm, Time Complexity, Space Complexity, etc.	Lab-01
2	Feb.27	Divide-and-Conquer (1) Mergesort, Selection, Master’s Theorem etc
2	Mar.02	Divide-and-Conquer (2) Sorting Network	Lab-02
3	Mar.06	Greedy Approach (1) Interval Scheduling, Interval Partitioning, Minimum Lateness, etc.
3	Mar.09	Greedy Approach (2) Matroid, Greedy-Max Algorithm	Lab-03
4	Mar.13	Greedy Approach (3) Matroid, Task Scheduling Problem
4	Mar.16	Dynamic Programming (1) Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc.	Lab-04
5	Mar.20	Dynamic Programming (2) RNA Secondary Structure, Sequence Alignment, etc.	Lab-05
5	Mar.23	Course Review Exercises, Midterm Review, Applications, etc
6	Mar.27	Midterm Exam	Midterm
6	Mar.30	Amortized Analysis (1) Aggregate Analysis, Accounting Method
6	Apr.01	Amortized Analysis (2) Potential Method, Dynamic Table, etc	Lab-06
7	Apr.03	Holiday
7	Apr.06	Graph Algorithms (1) Searching and Exploration, etc
8	Apr.10	Graph Algorithms (2) Single Source Shortest Patha, (Greedy and DP) etc
8	Apr.13	Graph Algorithms (3) All-Pairs Shortest Path, etc.	Lab-07
9	Apr.17	Graph Algorithms (4) Maximum Flow, Minimum Cut, etc.
9	Apr.20	NP-Completeness (1) NP Class, Polynomial Time, etc.	Lab-08
10	Apr.24	NP-Completeness (2) Reducibility, Proof, etc,
10	Apr.27	Approximation Algorithm(1) Basic Concepts, Greedy Design	Lab-09
11	May 01	Holiday
11	May 04	Approximation Algorithm(2) Dynamic Programming, Analytical Skills	Lab-10
12	May 08	Approximation Algorithm(3) Local Search, LP Rounding, Application
12		Review. Final Exam

作业与课后阅读 (Assignments and Readings)

Lecture 1: Preliminary - Basic Mathematical Objects

Reading Materials
- Syllabus & Grading Policy: Syllabus-Algorithm.pdf
- Slide01-Preliminary: Slide01-Preliminary.pdf
- Slide Print Version: 01-Preliminary.pdf
- Reference: Chapter 2 in "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002. Reference01-Proof.pdf
Lab 0: Self-Introduction
- Please complete your Self-Introduction (Due: 02/23/2017)
- Click the "Log-In" button at the top-right of this webpage then update your information.

Lecture 2: Algorithm Analysis

Reading Materials
- Slide02-AlgorithmAnalysis: Slide02-AlgorithmAnalysis.pdf
- Slide Print Version: 02-AlgorithmAnalysis.pdf
- Reference: Chapter 1 in "Algorithm Design Technique and Analysis" by M. H. Alsuwaiyel, World Scientific, 1999. Reference02-AlgorithmAnalysis.pdf
Latex Tutorial
- Latex Help Document (English): LatexHelper(ENG).pdf
- Latex Help Document (Chinese): LatexHelper(CHI).pdf
- Algorithm Package: AlgorithmPackage.pdf
- Algorithm Sample: AlgorithmSample.pdf
- Algorithm Sample Source: AlgorithmSample.tex
Lab 1: Algorithm Analysis
- Lab01-AlgorithmAnalysis: Lab01-AlgorithmAnalysis.pdf
- Latex Source: Lab01-AlgorithmAnalysis.tex
- Lab01-Solution: Lab01-Solution.pdf

Lecture 3: Divide and Conquer

Reading Materials
- Slide03-DivideConquer: Slide03-DivideConquer.pdf
- Slide Print Version: 03-DivideConquer.pdf
- Reference: Chapter 2 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007. Reference03-DivideConquer.pdf

Lecture 4: Sorting Network

Reading Materials
- Slide04-SortingNetwork: Slide04-SortingNetwork.pdf
- Slide Print Version: 04-SortingNetwork.pdf
- Reference: Chapter 27 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2002. (2nd Edition) Reference04-SortingNetwork.pdf
Lab 2: Divide and Conquer (Due: 10:00am, 03/06/2017)
- Lab02-DivideConquer: Lab02-DivideConquer.pdf
- Latex Source: Lab02-DivideConquer.tex
- Lab02-Solution: Lab02-Solution.pdf

Lecture 5: Greedy Strategy

Reading Materials
- Slide05-GreedyAlgorithm: Slide05-GreedyAlgorithm.pdf
- Slide Print Version: 05-GreedyAlgorithm.pdf
- Reference: Chapter 4.1-4.3, 4.5, 4.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. Reference05-GreedyAlgorithm.pdf

Lecture 6: Matroid

Reading Materials
- Slide06-Matroid: Slide06-Matroid.pdf
- Slide Print Version: 06-Matroid.pdf
- Reference: Chapter 16.4-16.5 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. Reference06-Matroid.pdf
Lab 3: Greedy Strategy (Due: 10:00am, 03/13/2017)
- Lab03-GreedyStrategy: Lab03-GreedyStrategy.pdf
- Latex Source: Lab03-GreedyStrategy.tex
- Lab03-Solution: Lab03-Solution.pdf

Lecture 7: Dynamic Programming

Reading Materials
- Slide07-DynamicProgramming: Slide07-DynamicProgramming.pdf
- Slide Print Version: 07-DynamicProgramming.pdf
- Reference: Chapter 6.1-6.7 in "Algorithm Design " by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. Reference07-DynamicProgramming.pdf
Lab 4: Matroid (Due: 10:00am, 03/20/2017)
- Lab04-Matroid Lab04-Matroid.pdf
- Latex Source Lab04-Matroid.tex
- Lab04-Solution Lab04-Solution.pdf

Lecture 8: Dynamic Programming (2)

Lab 5: Dynamic Programming (Due: 10:00am, 3/23/2017)
- Lab05-DynamicProgramming Lab05-DynamicProgramming.pdf
- Latex Source Lab05-DynamicProgramming.tex
- Lab05-Solution Lab05-Solution.pdf

Lecture 9: Amortized Analysis

Reading Materials
- Slide08-AmortizedAnalysis: Slide08-AmortizedAnalysis.pdf
- Slide Print Version 08-AmortizedAnalysis.pdf
Lab 6: Amortized Analysis (Due: 10:00am, 04/06/2017
- Lab06-AmortizedAnalysis Lab06-AmortizedAnalysis.pdf
- Latex Source Lab06-AmortizedAnalysis.tex
- Lab06-Solution Lab06-Solution.pdf

Lecture 10: Graph Algorithms

Reading Materials
- Slide09-GraphAlgorithms: Slide09-GraphAlgorithms.pdf
- Slide Print Version: 09-GraphAlgorithms.pdf

Lecture 11: Graph Exploration

Reading Materials
- Slide10-BFSDFS: Slide10-BFSDFS.pdf
- Slide Print Version: 10-BFSDFS.pdf
- Reference: Chapter 3, 4 in "Algorithm" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, McGraw-Hill, 2007. Reference09-GraphDecomposition.pdf

Lecture 12: Shortest Path

Shortest Path -- Greedy
- Slide11-ShortestPath: Slide11-ShortestPath.pdf
- Slide Print Version: 11-ShortestPath.pdf
- Reference: part of Chapter 24 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition): Reference10-ShortestPath.pdf
Shortest Path -- DP
- Slide12-ShortestPathDP: Slide12-ShortestPathDP.pdf
- Slide Print Version: 12-ShortestPathDP.pdf
- Reference: Chapter 6.8, 6.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. Reference11-ShortestPathDP.pdf
All-Pair Shortest Path
- Slide13-AllPair: Slide13-AllPair.pdf
- Slide Print Version: 13-AllPair.pdf
- Reference: Chapter 25 in "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, The MIT Press, 2009. (3rd Edition). Reference12-AllPairShortestPath.pdf
Lab 7: Shortest Path (Due: 10:00am, 04/17/2017)
- Lab07-ShortestPath Lab07-ShortestPath.pdf
- Lab07-Data Lab07-data.txt
- Latex Source Lab07-ShortestPath.tex
- Lab07-Solution Lab07-Solution.pdf

Lecture 13: Max Flow and Minimum Spanning Tree

Max Flow and Min Cut
- Slide14-MaxFlow: Slide14-MaxFlow.pdf
- Slide Print Version: 14-MaxFlow.pdf
- Reference: Chapter 7.1-7.3 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. Reference13-NetworkFlow.pdf
Minimum Spanning Tree
- Slide15-MST: Slide15-MST.pdf
- Slide Print Version: 15-MST.pdf
- Reference: Chapter 4.5, 4.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. (Check Reference05-GreedyAlgorithm.pdf)

Lecture 14: NP and Reduction

Reading Materials
- Slide16-Reduction: Slide16-Recudtion.pdf
- Slide Print Version: 16-Reduction.pdf
- Reference: Chapter 8.1-8.4, 8.9-8.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. Reference14-Reduction.pdf
Lab 8: Flow and Reduction (Due: 10:00am, 04/24/2017)
- Lab08-Flow and Reduction Lab08-Flow and Reduction.pdf
- Latex Source Lab08-Flow and Reduction.tex
- Lab08-Solution Lab08-Solution.pdf

Lecture 15: Approximation I

Reading Materials
- Slide17-ApproximationI: Slide17-ApproximationI.pdf
- Slide Print Version: 17-ApproximationI.pdf
- Reference: Chapter 1.1, 2.1, 2.3 in "Design of Approximation Algorithms " by D. Williamson, and D. Shomoys, Cambridge University Press, 2010 Reference15-Approximation.pdf
Lab 9: Approximation (Due: 10:00am, 05/04/2017)
- Lab09-Approximation: Lab09-Approximation.pdf
- Latex Source: Lab09-Approximation.tex
- Lab09-Solution: Lab09-Solution.pdf

Lecture 16: Approximation II

Reading Materials
- Slide18-ApproximationII: Slide18-ApproximationII.pdf
- Slide Print Version: 18-ApproximationII.pdf
- Reference: Chapter 14 in "Approximation Algorithms" by V. Vazirani, Springer-Verlag, 2001. Reference16-ApproximationII.pdf
Lab 10: ApproximationII (Due: 10:00am, 05/08/2017)
- Lab10-ApproximationII: Lab10-ApproximationII.pdf
- Latex Source: Lab10-ApproximationII.tex
- Lab10-Solution Lab10-Solution.pdf

Project

Project (Submission Due: 5/19/2017; Demo Due: 5/23/2017)
- Input Case Example case_example.zip

提交引导 (Submission Guidelines)

请登录右上角的JAccount进行作业提交，登录后可以下载课件、提交作业。
Please log in by JAccountat the top right corner to download course materials and submit your homework.
作业只能提交一个文档，如果有多个文档请放在一个文件夹里，将其压缩成.rar或.zip文件。作业可以多次提交，每次上传版本会覆盖原来版本。可通过点击右上方“Check Hw.”一栏查看作业提交、成绩与反馈情况（建议下载检查上传版本)。
You can only submit ONE document for each homework. If there are multiple documents, please put them inside a folder, and compress it in the form of .rar or .zip You can submit homework multiple times, while the original submitted version will be covered by the latest submitted one. You can click on “Check Hw.”at the top right corner to check the homework submission, grade, and feedback.(Suggestion: You can download your submitted homework to check it.)
若已登录的情况下提示权限不足，请刷新或者注销后重新登录，若仍权限不足，请及时与助教联系。如出现无法提交、不懂操作、系统Bug等情况请与助教及时联系。
If it shows that you do not have access after you log in, please refresh the webpage or re-log in again. If it still does not work, please contact teaching assistants in time. If you have other problems, e.g., you cannot or don’t know how to submit your homework, or find Bugs please contact your teaching assistants in time.

分组活动说明 (Group Project Description)

分组活动细节 (Group Project Detail)

序号 (No.)	队名 (Team Name)	队员一 (Member 1)	队员二 (Member 2)	队员三 (Member 3)	题目 (Project)	时间 (Time)
1	Good Boy	余秦	RAZIUR RAH...	曹翼丰
2	DC	程峰	丁佳晨	刘学成
3	名字真难取	廖铭鼎	廖韬
4	NAIVE!	黄海鑫	梅熠杰	张奕喆
5	Kadison	黄凯欣	闫迪	顾章轩
6	愚人节组的队	王昭	李寿航	崔超
7	ANL小分队	江磊	储泉泉	陆尤静
8	ANL大分队	刘洋溯	林煜	汪博文
9	Arshazak	AHMAD ARIB...	SHAHZAD SA...	ATTA UL MU...
10	9527	张开明	蒋晨之	SHERMAN HU...
11	Rovers	徐阳	江杉
12	Matroid	蔡林金	刘畅	宋卓然
13	blablablabla	胡巧平	卢君苇	AKBAR MAJI...
14	nsec	李杰	孟岩	章玮
15	MoA	ADEEL ZAFA...	ABDULRHMAN...	DANIEL CAM...
16	Titans	徐彬	修宇亮	王旭东
17	爪牙	唐伟伦	彭光前	潘昊
18	a little contribution	许荣森	戴宗哲	钱刘宸
19	Knights of the Round Table	罗欣剑	贾帅杰	马家旭

学生名册与课堂记录 (Roster and Event)

Roster

Class Attendance Pictures

Class Project Pictures

引用材料 (Reference)

Algorithm
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, 2009.
- M. H. Alsuwaiyel, Algorithm Design Technique and Analysis, World Scientific, 1999.
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithm, McGraw-Hill, 2007.
- J. Kleinberg, and E. Tardos, Algorithm Design, Pearson-Addison Wesley, 2005.
- Alfred V. Aho, John E Hopcroft, Jeffery D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
- Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
- Henming Zou, The Way of Algorithms, China Machine Press, 2010.
Computational Complexity
- Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994.
- Theory of Computational Complexity, by Ding-Zhu Du, and Ker-I Ko, published by John Wiley & Sons, Inc., 2000.
- John Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 2002.
- Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006.
Approximation
- Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
- D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms, 2011.
- D.Z Du, K-I. Ko, and X.D. Hu, Design and Analysis of Approximation Algorithms, 2012.
Acknowledgement
- material Special thanks is given to Prof. Kevin Wayne, Prof. Charles E. Leiserson, Prof. Salah E. Elmaghraby, Prof. Neeraj Mittal, Prof. Ding-Zhu Du, Prof. Yuxi Fu, Prof. Yijia Chen, Prof. Pinyan Lu, Dr. Xiaojuan Cai for sharing their teaching materials.